package demo.practice.binary_tree;

import demo.practice.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Offer32 {

    public List<List<Integer>> levelOrder(TreeNode root) {



        List<List<Integer>> list = new ArrayList<>();
        if(root==null)
            return list;

        Stack<TreeNode> odd = new Stack<>();
        Stack<TreeNode> even = new Stack<>();

        odd.add(root);
        while (odd.size() > 0 || even.size() > 0) {

            List<Integer> cl = new ArrayList<>();
            while (odd.size() > 0) {
                TreeNode pop = odd.pop();
                cl.add(pop.val);
                if (pop.left != null)
                    even.add(pop.left);

                if (pop.right != null)
                    even.add(pop.right);
            }

            if (cl.size() > 0)
                list.add(cl);

            cl = new ArrayList<>();
            while (even.size() > 0) {
                TreeNode pop = even.pop();
                cl.add(pop.val);


                if (pop.right != null)
                    odd.add(pop.right);

                if (pop.left != null)
                    odd.add(pop.left);
            }

            if (cl.size() > 0)
                list.add(cl);

        }

        return list;
    }


}
